# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        lst1 = set()
        while p:
            lst1.add(p)
            p = p.parent

        while q:
            if q in lst1:
                return q
            q = q.parent


if __name__ == "__main__":
    pass
